class Point {
    constructor(public x: number, public y: number) { }
}

class KDNode {
    constructor(
        public point: Point,
        public axis: number,
        public left: KDNode | null = null,
        public right: KDNode | null = null
    ) { }
}

class KDTree {
    private root: KDNode | null = null;

    public build(points: Point[]): void {
        this.root = this.buildTree(points, 0);
    }

    private buildTree(points: Point[], axis: number): KDNode | null {
        if (points.length === 0) {
            return null;
        }

        const sortedPoints = points.slice().sort((a, b) => (axis === 0 ? a.x - b.x : a.y - b.y));
        const medianIndex = Math.floor(sortedPoints.length / 2);
        const medianPoint = sortedPoints[medianIndex];
        const nextAxis = (axis + 1) % 2;

        return new KDNode(
            medianPoint,
            axis,
            this.buildTree(sortedPoints.slice(0, medianIndex), nextAxis),
            this.buildTree(sortedPoints.slice(medianIndex + 1), nextAxis)
        );
    }

    public nearestNeighbor(point: Point): Point | null {
        let nearest = null;
        let minDistance = Infinity;

        this.findNearestNeighbor(this.root, point, nearest, minDistance);

        return nearest;
    }

    private findNearestNeighbor(node: KDNode | null, target: Point, nearest: Point | null, minDistance: number): void {
        if (node === null) {
            return;
        }

        const distance = this.calculateDistance(node.point, target);

        if (distance < minDistance) {
            nearest = node.point;
            minDistance = distance;
        }

        const axis = node.axis;

        if (axis === 0 ? target.x < node.point.x : target.y < node.point.y) {
            this.findNearestNeighbor(node.left, target, nearest, minDistance);
            if (axis === 0 ? node.point.x - target.x < minDistance : node.point.y - target.y < minDistance) {
                this.findNearestNeighbor(node.right, target, nearest, minDistance);
            }
        } else {
            this.findNearestNeighbor(node.right, target, nearest, minDistance);
            if (axis === 0 ? target.x - node.point.x < minDistance : target.y - node.point.y < minDistance) {
                this.findNearestNeighbor(node.left, target, nearest, minDistance);
            }
        }
    }

    private calculateDistance(point1: Point, point2: Point): number {
        const dx = point1.x - point2.x;
        const dy = point1.y - point2.y;

        return Math.sqrt(dx * dx + dy * dy);
    }
}
